package uebung3;


public class BinTree<K extends Comparable<K>, D> {
	
	public static void main(String[] args) {
		
		BinTree<String,StudentBase> b = new BinTree<String,StudentBase>();
		for(int i=0;i<100000;++i){
			b.insert("student"+i,new InfStud(20000+i,"name"+i,"vorname"+i,new Date((int)(30*Math.random()*10),(int)(12*Math.random()*10),(int)(30*Math.random()*10))));
		}
		b.remove("student0");
		System.out.println(b.size());
	}
		
	class Node {
		public Node(K key, D data) {
			m_Key = key;
			m_Data = data;
		}

		K m_Key;
		D m_Data;
		Node m_Left = null;
		Node m_Right = null;
	}

	private Node m_Root;
	
	public void printRoot(){
		System.out.println("Key= "+m_Root.m_Key);
		System.out.println("Data= "+m_Root.m_Data);
	}
	
	public void printKeys(){
		printKeys_help(m_Root);
	}
	
	public void printKeys_help(Node n){
		if(n!=null){
			System.out.println(n.m_Key);
			printKeys_help(n.m_Left);
			printKeys_help(n.m_Right);
		}
	}
	
	public void printData(){
		printData_Help(m_Root);
	}
	
	private void printData_Help(Node n){
		if(n!=null){
			System.out.println(n.m_Data);
			printData_Help(n.m_Left);
			printData_Help(n.m_Right);
		}
	}
	
	public K[] getKeys(){
		K[] keys = (K[])new Object[size()];
		getKeys_help(m_Root,keys,0);
		return keys;
	}
	
	private void getKeys_help(Node n, K[] keys,int writePosition){
		if(n!=null){
			keys[writePosition]=n.m_Key;
			++writePosition;
			getKeys_help(n.m_Left,keys,writePosition);
			getKeys_help(n.m_Right,keys,writePosition);
		}
	}
	
	public int size() {
		return size_hlp(m_Root);
	}

	public int size_hlp(Node node) {
		if (node != null)
			return 1 + size_hlp(node.m_Left) + size_hlp(node.m_Right);
		else
			return 0;
	}
	
	public D searchRecursive(K key){
		 Node tmp = m_Root;
		 int res = key.compareTo(tmp.m_Key);
		 if(tmp!=null){
			 if(res<0)
				 searchRecursive(tmp.m_Left.m_Key);
			 if(res>0)
				 searchRecursive(tmp.m_Left.m_Key);
			 if(res==0)
				 return tmp.m_Data;
		 }
		return null;
	}
	
	public Node search(K key) {
		Node tmp = m_Root;
		while (tmp != null) {
			final int RES = key.compareTo(tmp.m_Key);
			if (RES == 0)
				return tmp;
			tmp = RES < 0 ? tmp.m_Left : tmp.m_Right;
		}
		return null;
	}

	public boolean insert(K key, D data) {
		NodeHandler h = new NodeHandler(m_Root);
		while(!h.isNull()){
			final int RES = key.compareTo(h.key());
			if(RES == 0)
				return false;
			h.down(RES<0);
		}
		h.set(new Node(key,data));
		return true;
	}

	class NodeHandler {
		Node m_Dad = null;
		Node m_Node = null;

		NodeHandler(Node n) {
			m_Node = n;
		}

		void down(boolean left) {
			m_Dad = m_Node;
			m_Node = left ? m_Node.m_Left : m_Node.m_Right;
		}

		boolean isNull() {
			return m_Node == null;
		}

		K key() {
			return m_Node.m_Key;
		}
	
		Node node() {
			return m_Node;
		}
		
		void set(Node n){
			if(m_Dad==null)
				m_Root=n;
			else if(m_Node!=null ? m_Node == m_Dad.m_Left : n.m_Key.compareTo(m_Dad.m_Key)<0)
				m_Dad.m_Left=n;
			else 
				m_Dad.m_Right=n;
			m_Node=n;
		}
	}
	
	public boolean remove(K key) {
		NodeHandler h = new NodeHandler(m_Root); // fange beim Vaterknoten an
		while (!h.isNull()) { // Solange dieser Knoten nicht Null ist
			final int RES = key.compareTo(h.key()); // Vergleiche zu suchenden
													// Schl�ssel mit dem
													// Schl�ssel des Knotens
			if (RES == 0) { // Schl�ssel gefunden
				if (h.node().m_Right == null) // ...dann gucke ob der Knoten
												// einen rechten Nachfolger hat
					h.set(h.node().m_Left); // ...setze Knoten auf linken
											// Nachfolger
				else {
					NodeHandler h2 = new NodeHandler(h.node());
					h2.down(false);
					while (h2.node().m_Left != null) {
						h.down(true);
					}
					h.node().m_Key = h2.node().m_Key;
					h.node().m_Data = h2.node().m_Data;
					h2.set(h2.node().m_Right);
				}
				return true;
			}
			h.down(RES < 0);
		}
		return false;
	}

	
	public SimpleCollection<D> getData(){
		SimpleCollection<D> data = new MyList<D>();
		getData_Help(m_Root,data);
		return data;
	}
	
	private void getData_Help(Node n, SimpleCollection<D> data){
		if(n!=null){
			data.push_back(n.m_Data);
			getData_Help(n.m_Right,data);
			getData_Help(n.m_Left,data);
		}
	}
	
	public void print(){
		print_help(m_Root);
	}
	 
	private void print_help(Node n){
				if(n!=null){
					System.out.println(n.m_Data);
					print_help(n.m_Left);
					print_help(n.m_Right);					
				}
	}
}
